package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-09-08 15:50
 */


/**
 * 题目：
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 * <p>
 * 示例：
 * 输入: n = 2
 * 输出: [0,1,1]
 * 解释:
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * <p>
 * <p>
 * 解题思路：
 * 如果当前num为奇数，则二进制中1的个数为前一个数二进制1的个数+1。 当前数为奇数，代表前一个数为偶数，所以前一个数的二进制最后一位一定是0，当前的数就是在它原来的基础上加了个1。
 * 例如，5(101)，上一个数为4(100), 5 = 4 + 1, 加上的1就是加到了二进制中的最后一位。
 * 如果当前num为偶数，则二进制中1的个数为 num/2 的二进制中1的个数。 这一灵感来源于位运算。例如 (1)0001 左移一位后变为 2(0010)，2(0010)左移一位后变为4(0100)，他们的1的个数都是不变的,只是位置在变化。
 */
public class Test14_前n个数字二进制中1的个数 {
    public int[] countBits(int n) {
        int a[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) {
                a[i] = a[i / 2];
            } else {
                a[i] = a[i - 1] + 1;
            }

        }

        return a;
    }
}
